This invention relates to distributed services. More particularly, the invention relates to secure auction services.
Technology has replaced many human procedures with electronic ones. Unfortunately, much of the tradition, culture, and law that has been developed to provide protection in human procedures cannot readily be adapted to afford the same protection in electronic procedures. The study of cryptographic protocols can be viewed as a technical response to this loss of more traditional means of protecting ourselves.
While many proposals have been put forward to guide the transition to electronic commerce, most of these proposals provide for only simple transactions involving little negotiation or competition among buyers and sellers. In contrast, many financial vehicles, such as auctions, exchanges, and general markets, do not conform to this simplistic view of commerce. The transition to electronic commerce should not preclude such vehicles, but rather should make them more accessible. Such transition requires an effort to examine some of these financial vehicles to understand what is required to adequately implement them in electronic systems.
One example of financial vehicles is a sealed-bid auction. The sealed-bid auction is one in which secret bids are issued for an advertised item, and once the bidding period closes, the bids are opened and the winner is determined according to some publicly known rule (e.g., the highest bidder wins). Sealed-bid auctions are used, for example, in the auctioning of mineral rights to U.S. government-owned land, in the sale of artwork and real estate, and in the auctioning of government procurement contracts.
The study of sealed-bid auctions is motivated not only by their practical importance, but also by the novel security problems that they pose. First, central to the fairness of a sealed-bid auction is the secrecy of sealed bids prior to the close of the bidding period. That is, the timing of the disclosure of bids is crucial. Second, auctions require nonrepudiation mechanisms to ensure that payment can be collected from winning bidders, as evidenced by the fact that in a recent FCC auction of interactive video and data service licenses, 13 winning bidders defaulted on their bids, forcing a second auction to be held. Third, due to secrecy requirements surrounding sealed-bid auctions, it may be difficult for outsiders to have confidence in the validity of the auction. Fourth, some types of sealed-bid auctions should enable bidders to remain anonymous. These problems are only exacerbated when one considers the implementation of auctions in distributed computer systems, or the possibility of a corrupt insider in the auction house collaborating with bidders.
It is therefore an object of this invention to provide a secure distributed auction service that supports the submission of monetary bids for an auction and ensures the validity of the outcome, despite the malicious collaboration of arbitrarily many bidders and fewer than one-third of the auction servers comprising the service. The auction service should address all of the security issues mentioned above. In particular, the auction service should guarantee to declare the proper winning bidder, and to collect payment in the form of digital cash from only that bidder. It should also be guaranteed that no bid is revealed prior to the close of the bidding period. Moreover, it should be possible for bidders to submit anonymous bids. The resilience of the auction service to malicious auction servers can be leveraged to provide resilience to malfeasant auction house insiders. If, for example, each individual is allowed access to fewer than one-third of the servers, then corrupting an insider provides no advantage to a bidder in the auction. This reduces the incentive for buying off insiders in the auction house.
It is also an object of this invention to provide an efficient and practical approach to performing auctions. For example, the approach should be feasible using off-the-shelf workstations for auction servers, even for large auctions involving hundreds of bids.